package 位图;

import java.util.HashSet;

/**
 * @author ljb
 * @version 1.0
 * @Date 2024/12/6
 */
public class Code01_Bitset {

    // 位图的实现
    // 使用时num不要超过初始化的大小
    public static class Bitset{
        public int[] set;

    //  n个数字：0~n-1
    //  4个bit
    //  0...31 32...63 64...95 96...127
        public Bitset(int n){
            // a/b 如果结果想向上取整，可以写成 : (a+b-1)/b
            // 前提是a和b都是非负数
            set = new int[(n+31) / 32];
        }

        //num/32来确定num在哪个区间，
        // num%32来确定num所在哪个区间的32位中的哪一位
        public void add(int num){
            set[num/32] |= 1 << (num % 32);
        }

        public void remove(int num){
            set[num/32] &= ~(1 << (num % 32));
        }

        public void reverse(int num){
            set[num/32] ^= 1 << (num % 32);
        }

        //set[num/32] >> (num % 32)
        // 让这个数右移到最低位，然后与000...0001进行与运算，看是否等于1
        public boolean contains(int num){
            return ((set[num/32] >> (num % 32)) & 1) == 1;
        }
    }

    //    对数器测试
    public static void main(String[] args) {
        int n = 1000;
        int testTimes = 10000;
        System.out.println("测试开始...");
        // 实现的位图结构
        Bitset bitset = new Bitset(n);
        // 直接用HashSet做对比测试
        HashSet<Integer> hashSet = new HashSet<>();
        System.out.println("调用阶段开始......");
        for(int i = 0; i < testTimes; i++){
            double decide = Math.random();
            // number -> 0 ~ n-1，等概率得到
            int number = (int)(Math.random() * n);
            if(decide < 0.333){
                bitset.add(number);
                hashSet.add(number);
            }else if(decide < 0.666){
                bitset.remove(number);
                hashSet.remove(number);
            }else{
                bitset.reverse(number);
                if (hashSet.contains(number)) {
                    hashSet.remove(number);
                }else{
                    hashSet.add(number);
                }
            }
        }
        System.out.println("调用阶段结束......");
        System.out.println("验证阶段开始.........");
        for(int i = 0; i < n; i++){
            if(bitset.contains(i) != hashSet.contains(i)){
                System.out.println("出错了xxxxxx!");
            }
        }
        System.out.println("验证阶段结束.........");
        System.out.println("测试结束...");
    }
}
